package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_129_求根节点到叶节点数字之和 {
    @Test
    public void main() {

        System.out.println(sumNumbers(TreeNode.initRoot()));
    }

    /**
    题目：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
     每条从根节点到叶节点的路径都代表一个数字：
     例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
     计算从根节点到叶节点生成的 所有数字之和 。
     叶节点 是指没有子节点的节点。

     示例 1：
     输入：root = [1,2,3]
     输出：25
     解释：
     从根到叶子节点路径 1->2 代表数字 12
     从根到叶子节点路径 1->3 代表数字 13
     因此，数字总和 = 12 + 13 = 25

     示例 2：
     输入：root = [4,9,0,5,1]
     输出：1026
     解释：
     从根到叶子节点路径 4->9->5 代表数字 495
     从根到叶子节点路径 4->9->1 代表数字 491
     从根到叶子节点路径 4->0 代表数字 40
     因此，数字总和 = 495 + 491 + 40 = 1026

    分析：【P 💔】
       1.回溯法：深度优先遍历，加上一个那啥 pathSum记录路径上的节点和
                --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
                --时长：5分钟

    边界值 & 注意点：
       1.
     **/
    int sum;
    public int sumNumbers(TreeNode root) {
        sum=0;
        dfs(root,0);
        return sum;
    }

    private void dfs(TreeNode root,int pathSum) {
        pathSum =  pathSum*10+root.val;
        if(root.left==null && root.right==null){
            sum+=pathSum;
        }else {
           if( root.left!=null)
               dfs(root.left,pathSum);
            if( root.right!=null)
               dfs(root.right,pathSum);
        }
    }
}
